import java.util.Deque;
import java.util.LinkedList;

class MyQueue{
    Deque<Integer> queue = new LinkedList<>();

    public void pop(int val) {
        if (!queue.isEmpty() && val == queue.peek()) {
            queue.poll();
        }
    }

    public void push(int val) {
        while (!queue.isEmpty() && val > queue.getLast()) {
            queue.removeLast();
        }
        queue.add(val);
    }
    public int peek() {
        return queue.peek();
    }
}
class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] ret = new int[nums.length - k + 1];
        MyQueue myQueue = new MyQueue();
        for (int i = 0; i < k; i++) {
            myQueue.push(nums[i]);
        }
        int num = 0;
        ret[num++] = myQueue.peek();

        for (int i = k; i < nums.length; i++) {

            myQueue.pop(nums[i - k]);

            myQueue.push(nums[i]);

            ret[num++] = myQueue.peek();
        }
        return ret;
    }

    public static void main(String[] args) {

    }
}

